/*
 问题说明
伊格内修斯做了一个恶梦昨晚。他发现自己对他的定时炸弹迷宫。迷宫有一个出口，伊格应该走出迷宫的炸弹爆炸之前。
炸弹的初始爆炸时间设定为6分钟。为了防止炸弹由摇爆炸，伊格不得不缓慢移动，即移动至从一个区域到最近的区域
（即，如果伊格看台上（X，Y）现在，他只能以（x + 1， y）时，（X-1，y）时，（X，Y + 1），或（X，Y-1）在下一分钟）
开他1分钟。一些地区在迷宫中包含了炸弹复位-设备。他们可以重置爆炸时间为6分钟。

鉴于迷宫和伊格内修斯“起始位置的布局，请告诉他依纳能否走出迷宫，如果他能，输出到达出口的最短时间，
他不得不用来寻找迷宫，否则输出-1

这里有一些规则：
1.我们可以假设迷宫是2个达阵。
2.每分钟，伊格只能到达最近的区域之一，他不应该走出边境，他当然不能走在墙上了。
3.如果伊格到达出口时，爆炸时间变为0，他不能得到迷宫出来。
4.如果伊格得到包含炸弹休息-设备时，爆炸时间变为0的区域，他不能使用的设备重置炸弹。
5.炸弹重置装备就能如你所愿如果需要使用多次，伊格可以到达任何区域中的迷宫多次如你所愿。
6.时间重置爆炸时间可忽略，换句话说，如果伊格得到含有炸弹休息-设备的区域，并且爆炸时间大于0，爆炸时间将被重置为6。

输入
输入包含多个测试用例。输入的第一行是一个单一的整数t是测试用例的数目。 T检验案例可循。
每个测试例开始两个整数N和M（1 <= N，Mm = 8）指示迷宫的大小。然后N行跟进，每行包含M个整数。数组表示迷宫的布局。
有五个整数这表明不同类型区域，在迷宫的：
0：该地区是一堵墙，伊格不应该在它走。
1：该区域包含什么，伊格可以在上面行走。
2：伊格'起始位置，伊格内修斯开始他逃离这个位置。
3：迷宫，依纳爵“目标位置的出口。
4：该区域包含了炸弹 - 复位 - 设备，伊格可以步行到这些区域的延迟时间爆炸。

输出
对于每一个测试用例，如果伊格可以得到迷宫出来，你应该输出他所需要的最短时间，否则你应该只是输出-1。

样本输入
4
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1
5 8
1 2 1 1 1 1 1 4 
1 0 0 0 4 0 0 1 
1 1 4 0 1 0 0 1 
1 0 0 0 0 3 0 1 
1 1 4 1 1 1 4 1
样本输出
4
-1
13
15
---------------------------------------------
test:
5
5 8
0 2 1 1 1 1 1 4 
1 0 0 0 4 0 0 1 
1 1 4 0 0 0 0 1 
1 0 0 0 0 3 0 1 
1 0 4 1 1 1 4 1
 */
package com.yuan.algorithms.acm201506;

import java.util.Scanner;

class Node {
	int x;
	int y;
	int currentTime;//当前使用时间
	int timeSum;//可用时间总量
	
	public Node(int x, int y, int currentTime, int timeSum) {
		this.x = x;
		this.y = y;
		this.currentTime = currentTime;
		this.timeSum = timeSum;
	}
}


class QueueArray {

	private static final int CAP = 10;// 队列默认大小
	private Object[] elements;// 数据元素数组
	private int capacity;// 数组的大小
	private int front;// 队首指针
	private int rear;// 队尾指针

	public QueueArray() {
		this(CAP);
	}

	public QueueArray(int cap) {
		capacity = cap + 1;//数组长度加1，用于区分队列满的情况
		elements = new Object[capacity];
		front = rear = 0;
	}

	/**
	 * 返回队列大小
	 * 
	 * @return
	 */
	public int getSize() {
		return (rear - front + capacity) % capacity;
	}

	/**
	 * 判断队列是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return front == rear;
	}

	/**
	 * 向队列添加数据
	 * @param e
	 */
	public void add(Object e) {
		// 判断队列是否存满了
		if (getSize() == capacity - 1) {
			expandSpace();// 扩展队列
		}
		elements[rear] = e;
		rear = (rear + 1) % capacity;
	}

	/**
	 * 扩展队列容量
	 */
	private void expandSpace() {
		Object[] temp = new Object[elements.length*2 - 1];//数组容量增大一倍
		int i = front;
		int j = 0;
		//将从front开始到rear前一个存储单元的元素复制到新数组
		while(i!=rear) {
			temp[j++] = elements[i];
			i = (i + 1) % capacity;
		}
		elements = temp;
		capacity = elements.length;
		front = 0;
		rear = j;//设置新的队尾指针
	}

	/**
	 * 队首元素出队
	 * @return
	 * @throws Exception
	 */
	public Object poll() throws Exception{
		if (isEmpty()) {
			throw new Exception("错误：队列为空");
		}
		Object obj = elements[front];
		elements[front] = null;//删除原来的数据
		front = (front+1)%capacity;//更新队首指针
		return obj;
	}
	
	/**
	 * 取队首元素（不删除元素）
	 * @return
	 * @throws Exception
	 */
	public Object peek() throws Exception{
		if (isEmpty()) {
			throw new Exception("错误：队列为空");
		}
		return elements[front];
	}
}


public class HD1072逃离炸弹迷宫 {

	static int[][] map;
	static int[][] mark;//标记进入该地区离爆炸所剩的时间
	static final int[] var = {1,0,0,1,-1,0,0,-1};
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int t = sc.nextInt();
			while(t-->0) {
				int n = sc.nextInt();
				int m = sc.nextInt();
				map = new int[m][n];
				mark = new int[m][n];
				int startX = 0, startY = 0;
				//接收地图
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < m; j++) {
						map[j][i] = sc.nextInt(); 
						if (map[j][i]==2) {
							startX = j;
							startY = i;
						}
					}
				}
				System.out.println(Bfs(startX, startY));
			}
		}
	}
	private static int Bfs(int startX, int startY) throws Exception {
		//Queue<Node> queue = new <Node>LinkedList();
		QueueArray queue = new QueueArray();
		Node origin = new Node(startX, startY, 0, 6);
		queue.add(origin);
		while(!queue.isEmpty()) {
			Node temp = (Node) queue.poll();
			//判断是否还有时间
			boolean timejudge = temp.timeSum > 0;
			if (!timejudge) {
				continue;
			}
			//在炸弹爆炸前找到出口
			if (temp.timeSum>0 && map[temp.x][temp.y]==3) {
				return temp.currentTime;
			}
			if (map[temp.x][temp.y]==4) {
				temp.timeSum = 6;//遇到炸弹重置装置
			}
			for (int i = 0; i < 4; i++) {
				int newX = temp.x+var[i*2];
				int newY = temp.y+var[i*2+1];
				//判断下标是否越界
				boolean indexJudge = (newX>=0 && newX<map.length) && (newY>=0 && newY<map[0].length);
				if (!indexJudge) {
					continue;
				}
				//如果进入该地区离上次进入该地区的爆炸时间不比上次多，则舍弃
				if (temp.timeSum <= mark[newX][newY]) {
					continue;
				}
				//判断该位置是否可以通过
				boolean mapJudge = map[newX][newY] == 1 || map[newX][newY] == 4 || map[newX][newY] == 3;
				if (mapJudge) {
					queue.add(new Node(newX, newY, temp.currentTime+1, temp.timeSum-1));
					mark[temp.x][temp.y] = temp.timeSum; //记录进入当前地区离爆炸所剩的时间
				}
			}
		}
		return -1;
	}

}
